#include <iostream>  
#include <vector>  
#include <climits>
#include "coin.h"  

int main() {  
    Coin coin;  
    int a1,a2,a3,a4,target;  
    std::cout << "输入1美分硬币数目: ";  
    std::cin >> a1;    
    std::cout << "输入5美分硬币数目: ";  
    std::cin >> a2;  
    std::cout << "输入10美分硬币数目: ";  
    std::cin >> a3;  
    std::cout << "输入25美分硬币数目: ";  
    std::cin >> a4;  
    std::cout << "输入目标总金额: ";  
    std::cin >> target;  
    int result = coin.min(a1, a2, a3, a4, target);  
    if(result==-1){
        std::cout << "无法凑齐目标金额" << std::endl;  
    }
    else{
        std::cout << "最小硬币数量：" << result << std::endl;  
    }
    return 0;  
} 

int Coin::min(int a1, int a2, int a3, int a4, int target) {  
    int i,j,k;
    std::vector<int> coins = {1, 5, 10, 25};  //初始设置钱币面值
    std::vector<int> number = {a1, a2, a3, a4};  //初始设置钱币数量
    std::vector<int> dp(target + 1,target+1); // 初始化为正无穷  
    dp[0] = 0; // 初始化设置 目标金额为0时，所需硬币数量为0  
    for (i = 1; i <= target; i++) {  
        for (j = 0; j < 4; j++) {  
            for (k = 1; k <= number[j] && i >= k * coins[j]; k++) {  
                dp[i] = std::min(dp[i], dp[i - k * coins[j]] + k);  
            }  
        }  
    }  
  
    return (dp[target] > target) ? -1 : dp[target]; // 如果dp[target]大于target 返回-1 说明无法凑齐目标金额;反之返回dp[target]  
}  